# 设计RandomPool结构
# 【题目】 设计一种结构，在该结构中有如下三个功能:
# insert(key):将某个key加入到该结构，做到不重复加入
# delete(key):将原本在结构中的某个key移除
# getRandom(): 等概率随机返回结构中的任何一个key。
# 【要求】 Insert、delete和getRandom方法的时间复杂度都是O(1)

import random


class RandomPool:
    def __init__(self):
        self.size = 0
        self.key2idx = {}
        self.idx2key = {}

    def insert(self, key):
        if key not in self.key2idx:
            self.key2idx[key] = self.size
            self.idx2key[self.size] = key
            self.size += 1

    def delete(self, key):
        """
        用最后一个去填充删除的位置
        """
        if key in self.key2idx:
            delete_idx = self.key2idx[key]
            last_key = self.idx2key[self.size-1]
            self.key2idx[last_key] = delete_idx
            self.idx2key[delete_idx] = last_key
            self.key2idx.pop(key)
            self.idx2key.pop(self.size-1)
            self.size -= 1

    def get_random(self):
        if self.size == 0:
            return None
        idx = random.randint(0, self.size-1)
        return self.idx2key[idx]


if __name__ == "__main__":
    pool = RandomPool()
    pool.insert("li")
    pool.insert("shao")
    pool.insert("jie")
    print(pool.get_random())
    pool.delete("shao")
    print(pool.get_random())
    pool.delete("li")
    pool.delete("jie")
    print(pool.get_random())
